/*
 * Project: Sudoku Explainer
 * Copyright (C) 2006-2007 Nicolas Juillerat
 * 
 * Project: Sudoku Hint Engine for Android
 * Copyright (C) 2010-2013 Emanuel Moecklin
 * 
 * Available under the terms of the Lesser General Public License (LGPL)
 */
package com.onegravity.sudoku.solver.rules.wing;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import com.onegravity.sudoku.solver.HintResource;
import com.onegravity.sudoku.solver.R;
import com.onegravity.sudoku.solver.accumulator.HintsAccumulator;
import com.onegravity.sudoku.solver.accumulator.StopHintProductionException;
import com.onegravity.sudoku.solver.core.IndirectHintProducer;
import com.onegravity.sudoku.solver.data.Cell;
import com.onegravity.sudoku.solver.data.Grid;
import com.onegravity.sudoku.solver.util.BitSetFactory;
import com.onegravity.sudoku.solver.util.Permutations;

/**
 * Implementation of the Wing solving techniques:
 * - degree 2: XY-Wing
 * - degree 3: XYZ-Wing
 * - degree 4: WXYZ-Wing
 * - degree 5: VWXYZ-Wing
 * - degree 6: UVWXYZ-Wing
 * - degree 7: TUVWXYZ-Wing
 * - degree 8: STUVWXYZ-Wing
 * - degree 9: RSTUVWXYZ-Wing
 * etc.
 */
public class WingProducer implements IndirectHintProducer {

	private final int degree;
	private final int nrOfPincherCells;				// nr of pincher cell for this wing
	private final int nrOfCandidates;				// nr of involved candidates
	private final int nrOfCommonCandWithPivot;		// nr of common candidates between pivot and each pincher

    public WingProducer(int degree) {
        this.degree = degree;
        this.nrOfPincherCells =			(degree==2) ? 2 : degree-1;
        this.nrOfCandidates =			(degree==2) ? 3 : degree;
        this.nrOfCommonCandWithPivot =	(degree==2) ? 1 : 2;
    }

    @Override
    public void getHints(Grid grid, HintsAccumulator accu) throws StopHintProductionException, InterruptedException {
    	if (degree<2) return;
    	// (1) find a potential pivot cell
        for (int y = 0; y < 9; y++) {
            for (int x = 0; x < 9; x++) {
                if (Thread.interrupted()) throw new InterruptedException();
                Cell pivotCell = grid.getCell(x, y);
                BitSet pivotCandidates = pivotCell.getPotentialValues();
                if (pivotCandidates.cardinality() == degree) {
                	
                	// (2) potential pincher cells have exactly 2 candidates
                	// (3) pincher candidates must be pivot cell candidates too (except in XY-Wings)
                	List<Cell> potentialPincers = findPotentialPincers(pivotCell);
                	// (4) we need a minimum amount of pinchers for this wing
                	if (potentialPincers.size()>=nrOfPincherCells) {
                		
                		// (5) check all permutations of pincer cells for a Wing pattern
                        Permutations perm = new Permutations(nrOfPincherCells, potentialPincers.size());
                        while (perm.hasNext()) {
                            int[] indicesArray = perm.nextBitNums();
                            int zValue = isWing(pivotCell, potentialPincers, indicesArray);
                            if (zValue>=1) {
                            	
                            	// (6) found a Wing now let's check if there are any candidates to remove
                            	ArrayList<Cell> pincerCells = new ArrayList<Cell>(); 
                            	for (int index:indicesArray) {
                            		pincerCells.add( potentialPincers.get(index) );
                            	}
                            	Map<Cell,BitSet> removablePotentials = getRemovablePotentials(pivotCell, pincerCells, zValue);
                            	if (removablePotentials.keySet().size()>0) {
                            		WingHint hint = new WingHint(removablePotentials, degree, pivotCell, pincerCells, zValue, grid.hasExtraRegions(), grid.isJigsaw());
                            		if (hint.isWorth()) accu.add(hint);
                            	}
                            	
                            } // if (zValue>=1) {
                            
                        } // while (perm.hasNext()) {
                        
                	} // if (potentialPincers.size()+1>=degree) {
                	
                } // if (pivotCandidates.cardinality() == degree) {
            } // for (int x = 0; x < 9; x++) {
        } // for (int y = 0; y < 9; y++)
    }

    /**
     * Find all potential pincer cells for a given pivot cell:
     *  (1) must have exactly two candidates
     *  (2) all candidates must be pivot cell candidates (except in XY-Wings)
     */
    private List<Cell> findPotentialPincers(Cell pivotCell) {
    	ArrayList<Cell> potentialPincers = new ArrayList<Cell>();
    	BitSet pivotCandidates = pivotCell.getPotentialValues();
        for (Cell pincerCell : pivotCell.getHouseCells()) {
            BitSet pincerCandidates = pincerCell.getPotentialValues();
            if (pincerCandidates.cardinality()==2) {
            	BitSet tmp = (BitSet) pincerCandidates.clone();
            	tmp.and(pivotCandidates);
            	if (tmp.cardinality()==nrOfCommonCandWithPivot) {
                   	// potential pincer cell found
            		potentialPincers.add(pincerCell);
            	}
            }
        }
    	return potentialPincers;
    }

    /**
     * Check if potential pincer cells are pincer cells for a given pivot cell 
     * @param pivotCell The pivot cell
     * @param potentialPincers A list of all potential pincer cells for the given pivot cell
     * @param indicesArray array indicating which potential pincer cells we want to check
     * @return the z value for the wing or -1 if it's not a wing pattern
     */
    private int isWing(Cell pivotCell, List<Cell> potentialPincers, int[] indicesArray) {
    	if (indicesArray.length<nrOfPincherCells) return -1;
    	BitSet union = new BitSet();
    	BitSet intersection = new BitSet();
    	intersection.set(1, 10);
    	for (int index:indicesArray) {
        	BitSet pincerCandidates = potentialPincers.get(index).getPotentialValues();
        	union.or(pincerCandidates);
        	intersection.and(pincerCandidates);
        }
		int zValue = intersection.nextSetBit(0);
		// XY-Wing pivot cells do NOT contain the z value!
		if (zValue>0 && degree==2 && pivotCell.getPotentialValues().get(zValue)) return -1;
    	return (union.cardinality()==nrOfCandidates) ? zValue : -1;
    }

    private Map<Cell,BitSet> getRemovablePotentials(Cell pivotCell, List<Cell> pincerCells, int zValue) {
        // Build list of removable potentials
        Map<Cell,BitSet> removablePotentials = new HashMap<Cell,BitSet>();
        Cell firstCell = (degree==2) ? pincerCells.get(0) : pivotCell;
        Set<Cell> victims = new LinkedHashSet<Cell>(firstCell.getHouseCells());
        for (Cell pincerCell:pincerCells) {
            victims.retainAll(pincerCell.getHouseCells());
            victims.remove(pincerCell);
        }
        for (Cell cell : victims) {
            if (cell.hasPotentialValue(zValue))
                removablePotentials.put(cell, BitSetFactory.createOneElement(zValue));
        }
        return removablePotentials;
    }
    
	@Override
	public String getProducerName() {
		int id = R.string.producer_xy_wings;
		switch(degree) {
		case 3: id =  R.string.producer_xyz_wings; break;
		case 4: id =  R.string.producer_wxyz_wings; break;
		case 5: id =  R.string.producer_vwxyz_wings; break;
		case 6: id =  R.string.producer_uvwxyz_wings; break;
		case 7: id =  R.string.producer_tuvwxyz_wings; break;
		case 8: id =  R.string.producer_stuvwxyz_wings; break;
		case 9: id =  R.string.producer_rstuvwxyz_wings; break;
		}
		return HintResource.getString(id);
	}
}